<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>单向链表</title>
</head>
<body>
<script>
    function LinkedList() {
        //内部类:节点类
        function Node(data) {
            this.data = data;
            this.next = null;
        }

        //属性
        this.head = null; //头节点(第一个节点)
        this.length = 0; // 链表长度

        /**
         * 追加方法
         */
        LinkedList.prototype.append = function (data) {
            let newNode  = new Node(data);
            //判断是否追加的是第一个节点
            if(this.length === 0 ) {
                this.head = newNode;
            }else {
                //不是第一个节点，则通过while找到最后一个节点，将next指向新节点(data)
                let current = this.head;
                while (current.next) {
                    current =current.next;
                }
                current.next = newNode;
            }
            this.length += 1;
        };

        /**
         *toString方法
         */
        LinkedList.prototype.toString = function () {
            let current = this.head;
            let listString = "";
            while (current) {
                listString += current.data + ' ';
                current = current.next;
            }
            return listString;
        };

        /**
         * insert方法
         */
        LinkedList.prototype.insert = function (position, data) {
            // 1.判断position是否正确
            if(position < 0 || position > this.length) {throw '插入位置有误!'}
            // 2.创建节点
            let newNode = new Node(data);
            // 3.判断插入位置是否是第一个
            if(position === 0) {
                newNode.next = this.head;
                this.head = newNode;
            }else {
                let index = 0;
                let current = this.head;
                let previous = null;
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }
                newNode.next = current;
                previous.next = newNode;
            }
            this.length += 1;
            return true;
        };

        /**
         * get方法
         */
        LinkedList.prototype.get = function (position) {
            // 1. 判断position是否正确
            if(position < 0 || position >= this.length) {return null}
            // 2.获取对应节点data
            let index = 0;
            let current = this.head;
            while (index++ < position) {
                current = current.next;
            }
            return current.data;
        };

        /**
         * indexOf方法
         */
        LinkedList.prototype.indexOf = function (data) {
            // 1.拿到头节点
            let current = this.head;
            let index = 0;
            // 2.开始查找
            while (current) {
                if(current.data === data) {
                    return index;
                }
                current = current.next;
                index += 1;
            }
            // 3.如果没有找到则返回-1
            return -1;
        };

        /**
         * update方法
         */
        LinkedList.prototype.update = function (position, data) {
            // 1.越界判断
            if(position < 0 || position >= this.length) {throw '要修改的节点找不到'}
            // 2.查找正确的节点
            let current = this.head;
            let index = 0;
            while (index++ < position) {
                current = current.next;
            }
            // 3.找到之后修改data
            current.data =data;
            return true
        };

        /**
         * removeAt方法
         */
        LinkedList.prototype.removeAt = function (position) {
            // 1.越界判断
            if(position < 0 || position >= this.length) {throw '要移除的节点找不到'}
            // 2.判断是否是第一个节点
            let current = this.head;
            if(position === 0) {
                this.head = this.head.next;
            }else {
                let previous = null;
                let index = 0;
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.length -= 1;
            return current.data;
        };

        /**
         * remove方法
         */
        LinkedList.prototype.remove = function (data) {
            // 判断是否是第一个节点
            if(this.head.data === data) {
                this.head = this.head.next;
                this.length -= 1;
                return 0;
            }else {
                let current = this.head.next;
                let index = 1;
                let previous = this.head;
                // 开始查找
                while (current) {
                    if(current.data === data) {
                        previous.next = current.next;
                        this.length -= 1;
                        return index;
                    }
                    previous = current;
                    current = current.next;
                    index += 1;
                }
                return -1;
            }
        };

        /**
         * 判断是否为空
         */
        LinkedList.prototype.isEmpty = function () {
            return this.length === 0;
        };

        /**
         * size方法
         */
        LinkedList.prototype.size = function () {
            return this.length;
        }

    }
    let list = new LinkedList();
    list.append('aaa');
    list.append('bbb');
    list.append('ccc');
    list.append('ddd');
    list.append('fff');
    console.log(list.toString());
    list.insert(4, 'eee');
    console.log(list.toString());
    console.log(list.get(5));
    console.log(list.indexOf('ccc'));
    list.update(0, '我是第一个');
    console.log(list.toString());
    let t = list.removeAt(1);
    console.log(t);
    console.log(list.toString());
    let index = list.remove('fff');
    console.log(index);
    console.log(list.toString());
    console.log('链表长度：'+list.size())
</script>
</body>
</html>